package day68_other;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/7/16 21:55
 * @Version 1.0
 */
public class Solution {

    private boolean[] visited;

    public int NumberOfFriendsCircle(int[][] M) {
        this.visited = new boolean[M.length];

        int count = 0;
        for (int i = 0; i < M.length; i++){
            if (!visited[i]){
                dfs(M, i);
                count++;
            }
        }
        return count;
    }

    private void dfs(int[][] M, int idx){

        visited[idx] = true;
        int[] friend = M[idx];
        for (int i = 0; i < friend.length; i++) {
            if (friend[i] == 1 && !visited[i]){
                dfs(M, i);
            }
        }
    }
}
